package com.fanco.learn_datastruct_leetcode.leetcode;

import java.util.*;

/**
 * 给定一个无重复元素的正整数数组candidates和一个正整数target，找出candidates中所有可以使数字和为目标数target的唯一组合。
 *
 * candidates中的数字可以无限制重复被选取。如果至少一个所选数字数量不同，则两种组合是唯一的。
 *
 * 对于给定的输入，保证和为target 的唯一组合数少于 150 个。
 */
public class Day20 {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int [] nums = {1,2,7,8,9};
        int target = 9;
        List<List<Integer>> lists = solution.combinationSum(nums, target);
        lists.forEach(e -> {
            System.out.println(e.toString());
        });
    }

    private static class Solution {
        public List<List<Integer>> combinationSum(int[] candidates, int target) {

            int length = candidates.length;
            List<List<Integer>> res = new ArrayList<>();
            if (length == 0) {
                return res;
            }
            // 排序 方便剪枝
            Arrays.sort(candidates);

            Deque<Integer> path = new ArrayDeque<>();
            dfs(candidates, 0, length, target, path, res);

            return res;
        }

        private void dfs(int[] candidates, int begin, int length, int target, Deque<Integer> path, List<List<Integer>> res) {
            if (target == 0) {
                res.add(new ArrayList<>(path));
                return;
            }
            for (int i = begin; i < length; i++) {
                if (target - candidates[i] < 0) {
                    break;
                }
                path.addLast(candidates[i]);
                dfs(candidates, i, length, target - candidates[i], path, res);
                path.removeLast();
            }
        }
    }
}
